perm filename 28B[00,BGB] blob
sn#046272 filedate 1973-06-06 generic text, type T, neo UTF8
~F2
"The image tree is generated one threshold level at a time, starting at the
highest level (branch tips). At each level, the image is scanned, and the points
above the threshold are marked in a scratch array. This scatch array is then scanned
for marked points. When one is found, a contiguity routine is called, which visits
all marked points which can be reached from the start via a connected path. The
marks are erased by this routine as it goes, and statistics are kept on the region
thus generated, such as the sums of the x and y coordinates of the points, and the
sum of the squares of the x and y coordinates (used to compute the centerand the
eccentricity). A tree node is then made up for the region, and the scan for marked
points continues. A special mark is left in the scratch array for each region. When
this mark is encountered during the scan at the next level, it is looked up on an
association list. This establishes the link between a region and the regions which
are a subset of it at the previous level - i.e. between a node and its sub-nodes."
"The contiguity scan is the most complex program. It works by leaving
directional pointers in the scratch array. These are three-bit codes denoting one of
the eight possible neighboring points. The contiguity scan is always started at a
point which is on the bottom edge of the region. It traces along this edge to the
right by moving from one marked point to the next, but always keeping an un-marked
point to the right side. As it goes, it erases the marks, so that for a region with
smooth boundaries, it will follow a spiral path to the center, "eating up" the marks
as it goes, like a lathe with the tool continually advancing into the work."
"As the contiguity routine scans, it lays down back pointers in the scratch
array which enable it to retrace its path back to the start. If a dead end is
reached (no more marked neighbors), it traces back along this path, looking for
marked points to the right. There can be no marked points on the left side while
backtracking, since this was the right side on the way out, and the outgoing scan
stayed as far to the right as possible. If a marked point is found on the backtrace,
it is replaced with a pointer to the adjacent path already traced out, and then a new
path is traced as if this were a new starting point. When the backtrace reaches the
original starting point, the contiguity scan is completed. The effect of this
algorithm is to construct a tree of pointers in the scratch array, with the starting
point at the root. All points which can be reached via a connected path from the
starting point will be a part of this tree."